import { ListNode, arrToList, listToArr } from "../../utils/listUtil.js";

/** 2.两数相加
 *  @description 
 *- 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
 *- 请你将两个数相加，并以相同形式返回一个表示和的链表。
 *- 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。 
 */
export function addTwoNumbers(l1: ListNode | null = arrToList([7, 5, 6]), l2: ListNode | null = arrToList([4, 5, 6])): ListNode | null {
  /**判断是否需要进位+1 */
  let need = false
  /**固定的头指针 */
  const head = new ListNode()
  /**新链表的指针 */
  let cur = head
  while (l1 || l2) {
    let sum: number = (l1?.val || 0) + (l2?.val || 0) + (need ? 1 : 0)
    need = sum >= 10
    cur.next = new ListNode(sum % 10);
    cur = cur.next
    if (l1) l1 = l1.next
    if (l2) l2 = l2.next
  }
  if (need) cur.next = new ListNode(1)
  return head.next
}
/**19. 删除链表的倒数第 N 个结点 */
export { removeNthFromEnd } from '../双指针/index.js'
/**21. 合并两个有序链表
 * - 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
 */
export function mergeTwoLists(list1: ListNode | null = arrToList([1, 2, 4]), list2: ListNode | null = arrToList([1, 3, 4])): ListNode | null {
  const head = new ListNode()
  let node = head
  while (list1 || list2) {
    //如有一个已经空了，那就直接合并剩下的
    if (!list1) {
      node.next = list2
      break
    }
    if (!list2) {
      node.next = list1
      break
    }

    if (list1.val >= list2.val) {
      node.next = list2
      list2 = list2.next
    } else {
      node.next = list1
      list1 = list1.next
    }
    node = node.next

  }
  return head.next
}
/**23. 合并 K 个升序链表
 * - 给你一个链表数组，每个链表都已经按升序排列。
 * - 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 */
export function mergeKLists(lists: Array<ListNode | null> = [arrToList([1, 4, 5]), arrToList([1, 3, 4]), arrToList([2, 6])]): ListNode | null {
  //当成两两合并

  if (lists.length === 0) return null
  for (let i = lists.length - 1; i >= 0; i--) {
    lists[lists.length - 2] = mergeTwoLists(lists[i], lists[i - 1]) //使用21题的代码
    lists.length--
  }
  return lists[-1]


  // 用容量为K的最小堆优先队列，把链表的头结点都放进去，然后出队当前优先队列中最小的，挂上链表，，然后让出队的那个节点的下一个入队，再出队当前优先队列中最小的，直到优先队列为空。
  class PriorityQueue {
    queue: ListNode[] = [];
    constructor(initList?: (ListNode | null)[]) {
      initList?.forEach(this.in)
    }
    in = (node: ListNode | null) => {
      if (!node) return
      this.queue.push(node)
      this.queue.sort((a, b) => a.val - b.val)
      console.log(this.queue);
    }
    out() {
      return this.queue.shift()
    }
  }
  const list = new PriorityQueue(lists)
  const vHead = new ListNode(0)
  let cur = vHead
  while (list.queue.length) {
    const temp = list.out()!
    cur.next = temp
    if (temp.next) {
      list.in(temp.next)
    }
    cur = cur.next!
  }
  return vHead.next
}
/**24. 两两交换链表中的节点
 * - 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
 * - 输入：head = [1,2,3,4]
 * - 输出：[2,1,4,3] 
 */
export function swapPairs(head: ListNode | null = arrToList([1, 2, 3, 4])): ListNode | null {
  const vHead = new ListNode(0, head)
  let cur = vHead
  //思路就是，cur不动，移动 下俩个。 注意需要保存第三个的引用，不然会丢失
  while (cur && cur.next && cur.next.next) {
    //画图理解  0->1->2->3
    const temp1 = cur.next //1
    const temp2 = cur.next.next //2
    const temp3 = cur.next.next.next //3
    temp2.next = cur.next //先把2和1连起来
    cur.next = temp2//连上0和2
    temp1.next = temp3//1连上3 （实现交换了）
    cur = cur.next.next!
  }
  return vHead.next



  //思路：不是移动cur，而是去交换 cur 的下两个

  // type node = ListNode | null
  // const dommyHead: node = new ListNode(0, head)//创建虚拟头结点，指向原本的head
  // let cur: node = dommyHead//这个指针用于移动，保持原本的虚拟头结点不动
  // while (cur.next && cur.next.next) {//因为操作需要用到 .next 和 .next.next
  //   const tem1: node = cur.next//这个节点是“交换前的左节点”，会和tem1.next进行交换
  //   const tem2: node = cur.next.next.next //这个节点是 “交换前的右节点”的右节点，用于保存交换完成后应该的的next指向，实际上本轮交换不会动tem2指向的内容

  //   //假设这一轮是 虚->1->2->3->4，那么tem1指向1，tem2指向3，cur指向虚拟头结点
  //   cur.next = cur.next.next//把cur的next替换为2（也就是说，这个2变为了交换后的左节点）
  //   // 经过上面这一步，现在有两条链子 主链: 虚->2->3->4 和 副链: 1->2->3->4，cur指向虚
  //   cur.next.next = tem1//原本主链的2指向3 变为了2指向1 把两条链子串起来了
  //   // 经过上面这一步，把两条串起来了  虚->2->1->2->3->4 ，cur指向虚，tem2指向3
  //   cur.next.next.next = tem2//然后把1.next=tem2(也就是3，把第二个2删了)，才完成交换，且不影响其它节点
  //   // 经过上面这一步，把两条串起来了  虚->2->1->3->4 ，cur指向虚，tem2指向3

  //   // 最后要把cur往后移动两位，才不会影响到已经被交换的节点
  //   cur = cur.next.next
  // }
  // return dommyHead.next //返回虚拟头结点的下一个，也就是现在真正的头节点
}
/**25. K 个一组翻转链表
 * - 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
 * - 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序
 */
export function reverseKGroup(head: ListNode | null = arrToList([1, 2]), k: number = 2): ListNode | null {
  // 思路：借助 206题的函数，我们遍历链表，遇到k个就反转一次。复杂的地方就在于，反转前后的指针指向，需要画图理解

  if (k === 1) return head
  /**反转一个链表 - 206题的代码 */
  function reverseList(head: ListNode | null): ListNode | null {
    let pre: typeof head = null
    let cur = head
    while (cur) {
      const temp = cur.next
      cur.next = pre
      pre = cur
      cur = temp
    }
    return pre
  }
  // 遍历链表，裁剪k个出来反转。
  const vHead = new ListNode(0, head)
  let lastHead = vHead //上一个链表的末尾，便于拼接 （其实是上一条末尾原本的头，反转了成为末尾了，方便拼接）
  let count = 0 //当前分组数量
  let cur = head //当前遍历到的节点
  let newHead = head // 需要被裁剪出来的新链表的头部
  while (cur) {
    count++
    if (count === 1) {
      newHead = cur //记录头部
    }
    if (count === k) {//到达一组了
      const temp = cur.next
      cur.next = null
      lastHead.next = reverseList(newHead)
      lastHead = newHead! // 为了下一次循环，这时候“newHead”其实就是下一轮循环的“lastHead” 
      cur = temp
      count = 0
    } else {
      cur = cur.next
    }
  }

  //已经走完了，如果发现有部分节点还凑齐k，就需要把这部分给合并到新链表上 

  if (count !== 0) lastHead.next = newHead //这里的 newHead 就是没被凑齐的部分的头结点
  // if (count > 0) preHead.next = reverse(curHead) //如果题目需要未满k的也反转

  return vHead.next
}
/**92. 反转链表II
 * - 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
 */
export function reverseBetween(head: ListNode | null, left: number, right: number): ListNode | null {
  const reverse = (node: ListNode | null) => {
    let pre = null
    let cur = node
    while (cur) {
      const temp = cur.next
      cur.next = pre
      pre = cur
      cur = temp!
    }
    return pre
  }
  let i = 0
  const vHead = new ListNode(0, head)
  let cur = head
  let startPre = vHead, startHead
  while (cur) {
    // left和right是从1开始计数
    if (i === left - 2) {
      startPre = cur
    } else if (i === left - 1) {
      startHead = cur
    }
    if (i === right - 1) {
      const temp = cur.next
      cur.next = null
      startPre!.next = reverse(startPre!.next)
      startHead!.next = temp
      cur = temp
    } else {
      cur = cur.next
    }
    i++
  }
  return vHead.next
}
/**142. 环形链表 II
 * - 链表若有环，则返回环开始的节点。
 */
export function detectCycle(head: ListNode | null): ListNode | null {
  //判断是否有环：可以使用快慢指针法，分别定义 fast 和 slow 指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。
  // 找这个环的入口：https://programmercarl.com/0142.环形链表II.html#思路

  let fast = head
  let slow = head
  while (fast && fast.next) {
    fast = fast.next.next
    slow = slow!.next
    if (fast === slow) {
      slow = head
      while (slow !== fast) {
        //记住：若相遇，让slow指针从头开始，fast指针步长改为1，相遇的地方就是入口。 （原理是数学题）
        fast = fast!.next
        slow = slow!.next
      }
      return slow
    }
  }
  return null
}
/**143. 重排链表
 * - 给定一个单链表 L 的头节点 head ，单链表 L 表示为： `L0 → L1 → … → Ln - 1 → Ln`
 * - 请将其重新排列后变为： `L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …`
 */
export function reorderList(head: ListNode | null): void {
  //找中点，断开，逆序后半段链表，再创建新链表
  /**反转链表 */
  const reserve = (node: ListNode | null) => {
    let pre: ListNode | null = null
    let cur: ListNode | null = node
    while (cur) {
      const temp = cur.next
      cur.next = pre
      pre = cur
      cur = temp
    }
    return pre
  }
  /**获得链表长度 */
  const getLength = (node: ListNode | null) => {
    let len = 0
    while (node) {
      node = node.next
      len++
    }
    return len
  }
  /**从中点断开，返回后半段 */
  const center = (node: ListNode | null, length: number) => {
    let index = 0
    while (index < (length >> 1)) {
      node = node!.next
      index++
    }
    const res = node!.next
    node!.next = null
    return res
  }
  const length = getLength(head)
  const after = center(head, length)
  const reserveList = reserve(after)
  // console.log(reserveList, head);
  /**原链表节点 */
  let orCur = head
  /**反转链表节点 */
  let reCur = reserveList
  while (orCur && reCur) {
    //比如 1-2-3-4 和 7-6-5
    //当前遍历到 orCur 1和 reCur 7
    //需要保存好 2 和 4的引用，然后把 拼接 1-7,7后面跟上2
    const orTem = orCur.next//保存2
    const reTem = reCur.next//保存6 
    reCur.next = orTem//拼接 7-2
    orCur.next = reCur // 拼接 1-7-2
    orCur = orTem //orCur来到2
    reCur = reTem //reCur来到6
  }
  // console.log(listToArr(head));


}
/**160. 相交链表
 * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
 */
export function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {

  //思路：让两端末尾对齐 
  const getLen = (node: ListNode | null) => {
    let len = 0
    while (node) {
      node = node.next
      len++
    }
    return len
  }
  let sizeA = getLen(headA)/// A的长度
  let sizeB = getLen(headB)// B的长度
  let curA = headA //A移动的指针
  let curB = headB //B移动的指针  
  //为了接下来的写代码方便，让sizeA和curA是最长的那条链表
  if (sizeA < sizeB) {
    [sizeA, sizeB] = [sizeB, sizeA];
    [curA, curB] = [curB, curA];
  }
  //计算长度差 （为了让两条链表末端对齐，因为要保证相交节点的后面全部相等，所以从短的链表开始比较才有意义）
  let gap = sizeA - sizeB;
  //移动最长的链表curA，让两条链表末端对齐 比如 12345 和 245，此时curA指向3，curB指向2
  while (gap-- && curA) {
    curA = curA.next;
  }
  //遍历两条处理后的链表
  while (curA && curB) {
    if (curA === curB) {//如果链表某个节点 地址 相同，代表后面的内容也会完全相同，那么返回即可
      return curA
    }
    curA = curA.next
    curB = curB.next
  }
  return null//遍历完没找到，就返回null
};
/**206. 反转链表
 * - 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 */
export function reverseList(head: ListNode | null = arrToList([1, 2, 3, 4, 5])): ListNode | null {
  // //思路，从前往后处理pre和cur，比如遍历到第二个的时候， pre就是它的前一个节点，把pre赋值给next，实现反转
  // let pre: ListNode | null = null
  // let cur = head
  // while (cur) {
  //     const temp = cur.next
  //     cur.next = pre
  //     pre = cur
  //     cur = temp
  // }
  // return pre
  function reverse(pre: ListNode | null, cur: ListNode | null) {
    if (cur === null) return pre //对应上面的 while (cur) 结束后的操作
    const temp = cur.next
    cur.next = pre
    return reverse(cur, temp)//递归就是双指针里的：pre = cur; cur = temp;
  }
  return reverse(null, head)//这里初始化调用，其实就是双指针里的：pre = null; cur = head;
}
/**707. 设计链表
 * - 设计自己的链表，要求实现get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex等方法
 */
export function myLinkedList() {
  class MyLinkedList {
    vHead: ListNode
    size: number
    constructor() {
      this.vHead = new ListNode(0)
      this.size = 0
    }

    /**获得指定下标的节点 */
    private getNode(index: number): ListNode {
      if (index === -1) return this.vHead
      let i = 0
      let p = this.vHead.next
      while (i < index) {
        p = p!.next
        i++
      }
      return p!
    }

    /**获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。 */
    get(index: number): number {
      if (index >= this.size) return -1
      return this.getNode(index).val
    }

    /**将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点 */
    addAtHead(val: number): void {
      const originHead = this.vHead.next
      this.vHead.next = new ListNode(val, originHead)
      this.size++
    }

    /**将一个值为 val 的节点追加到链表中作为链表的最后一个元素。 */
    addAtTail(val: number): void {
      const last = this.getNode(this.size - 1)
      last.next = new ListNode(val)
      this.size++
    }

    /**将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。 */
    addAtIndex(index: number, val: number): void {
      if (index > this.size) return
      if (index === this.size) this.addAtTail(val)
      else {
        const node = this.getNode(index - 1)
        node.next = new ListNode(val, node.next)
        this.size++
      }
    }

    /**如果下标有效，则删除链表中下标为 index 的节点。 */
    deleteAtIndex(index: number): void {
      if (index >= 0 && index < this.size) {
        const node = this.getNode(index - 1)
        node.next = node.next!.next
        this.size--
      }
    }
    log() {
      console.log(listToArr(this.vHead.next));
    }
  }


  const list = new MyLinkedList()
  list.addAtHead(1)
  list.log()
  list.addAtTail(3)
  list.log()
  list.addAtIndex(1, 2)
  list.log()
  console.log((list.get(1)));
  list.deleteAtIndex(0)
  list.log()
  console.log(list.get(0));
}
